package day0220

import . "gocode/algorithm/utils"

func hasCycle1(head *ListNode) bool {
	set := map[*ListNode]bool{}
	cur := head
	for cur != nil {
		if has := set[cur]; has {
			return true
		} else {
			set[cur] = true
		}
		cur = cur.Next
	}
	return false
}

func hasCycle(head *ListNode) bool {
	fast, slow := head, head
	for fast != nil && fast.Next != nil {
		slow = slow.Next
		fast = fast.Next.Next
		if slow == fast {
			return true
		}
	}
	return false
}

func detectCycle(head *ListNode) *ListNode {
	fast, slow := head, head
	for fast != nil && fast.Next != nil {
		slow = slow.Next
		fast = fast.Next.Next
		if slow == fast {
			for head != slow {
				head = head.Next
				slow = slow.Next
			}
			return slow
		}
	}
	return nil
}
